Con questo capitolo si apre la seconda parte del corso, dedicata ai problemi di decisione sequenziale e al reinforcement learning. Il cambio di prospettiva rispetto all’apprendimento supervisionato è radicale: non c’è più un dataset di esempi con la risposta corretta, ma un agente che interagisce con un ambiente, prova azioni, riceve valutazioni numeriche (reward) e deve imparare da solo un comportamento che massimizzi la qualità complessiva delle sue scelte nel tempo. Prima di poter parlare di algoritmi di apprendimento serve però un linguaggio matematico per descrivere il problema, ed è esattamente il contenuto di questo capitolo: il Processo Decisionale di Markov (Markov Decision Process, MDP). Il percorso parte dall’intuizione, formalizza l’ambiente attraverso la gerarchia processo di Markov, Markov Reward Process, MDP, definisce return e discount factor, introduce policy e value function, deriva le equazioni di Bellman con la loro soluzione in forma chiusa, affronta la nozione di policy ottima e arriva alle equazioni di ottimalità di Bellman, la cui non linearità è la porta d’ingresso agli algoritmi dei capitoli successivi; chiude un esempio interamente svolto su un piccolo MDP.

Riferimenti sul testo: Sutton e Barto, Reinforcement Learning: An Introduction, capitolo 3. Materiale complementare consigliato: il corso online Fundamentals of Reinforcement Learning (Coursera), su cui è modellata la presentazione di questi argomenti.

1. Imparare agendo: un tipo di apprendimento diverso#

1.1 Feedback istruttivo contro feedback valutativo#

Nell’apprendimento supervisionato il modello viene addestrato fornendogli l’output corretto: per ogni input del training set c’è la risposta giusta, e imparare significa avvicinarsi il più possibile a quella risposta. Alla domanda “qual è il nome dell’azienda che ha sviluppato ChatGPT?” corrisponde una e una sola risposta corretta, “OpenAI”, e il confronto tra output del modello e risposta corretta è ben definito.

Molti problemi reali non hanno questa struttura. Si pensi alla richiesta “scrivi un tweet di 140 caratteri su ChatGPT”: non esiste il tweet corretto. Esistono tweet migliori e tweet peggiori, e al massimo si può assegnare a ciascun output un punteggio, un voto, una preferenza. Il concetto di “giusto o sbagliato” viene sostituito dal concetto di “quanto è buono”: non si fornisce più al modello la soluzione, ma una valutazione della soluzione che il modello ha prodotto.

Idea chiave: nel reinforcement learning il modello non riceve mai l’output corretto, riceve solo un giudizio numerico sull’output che ha prodotto. Questo tipo di feedback si dice valutativo, in contrapposizione al feedback istruttivo del supervisionato.

Il feedback valutativo ha una conseguenza profonda: un punteggio dice quanto è buona l’azione provata, ma non dice se ne esistesse una migliore, né quale fosse. Per scoprirlo l’agente deve esplorare, cioè provare attivamente comportamenti alternativi e confrontarne le valutazioni. Nel supervisionato il problema dell’esplorazione non esiste, perché la risposta giusta è data; qui diventa parte integrante dell’apprendimento.

In parole semplici: il supervisionato è come studiare con un tutor che dà la soluzione di ogni esercizio; il reinforcement learning è come giocare a un videogioco sconosciuto in cui appare solo il punteggio. Nessuno spiega la mossa giusta: bisogna provare, guardare il punteggio e capire da soli che cosa funziona.

1.2 Le difficoltà delle decisioni sequenziali#

La seconda caratteristica del nuovo setting è la sequenzialità: in molti problemi l’output non è una singola risposta ma una sequenza di decisioni (o azioni) prese per raggiungere un obiettivo. Un programma che impara a giocare a scacchi deve produrre un’intera sequenza di mosse il cui esito, vittoria o sconfitta, si conosce solo alla fine. Le proprietà che rendono difficile questa classe di problemi sono:

• le azioni ottime dipendono dal contesto: la stessa mossa può essere ottima in una configurazione della scacchiera e pessima in un’altra; questo è analogo alla dipendenza dall’input nel supervisionato;
• non ci sono esempi di azioni corrette: in generale non è disponibile, e può essere impossibile da costruire, un archivio di “azioni giuste” per ogni situazione;
• le azioni hanno conseguenze a lungo termine: una decisione presa ora può influenzare le situazioni e i reward di molti passi futuri;
• le conseguenze immediate di un’azione ottima possono sembrare negative: a scacchi, sacrificare un pezzo è un danno immediato, ma può creare la posizione che vince la partita.

L’ultimo punto è il più insidioso e ha un nome: delayed reward (ricompensa ritardata). Il segnale che certifica la bontà di una scelta può arrivare molte mosse dopo la scelta stessa, e l’algoritmo deve riuscire ad attribuire il merito (o la colpa) del risultato finale alle azioni giuste lungo la sequenza; questo problema di attribuzione è noto come credit assignment.

Un esempio giocattolo aiuta a fissare le idee. Un pesce artificiale deve sopravvivere nel suo ambiente: mangiare plancton vale $+3$, mangiare un verme vale $+10$, avvicinarsi allo squalo vale $-100$. Il comportamento buono dipende dal contesto: se il verme è vicino allo squalo, la scelta golosa del $+10$ immediato può portare al $-100$, e conviene ripiegare sul plancton.

In parole semplici: non basta valutare ogni singola azione con il premio che frutta subito, perché le azioni buone oggi possono costare care domani e viceversa. Il problema vero è collegare i premi e le punizioni, che possono arrivare molto tardi, alle decisioni che li hanno causati.

1.3 L’interfaccia agente-ambiente#

Il modo standard di inquadrare questi problemi è separare il sistema in due entità che interagiscono ciclicamente:

• l’agente è l’entità che apprende e decide: il programma, il modello che si sta costruendo;
• l’ambiente è tutto ciò che sta fuori dall’agente: riceve le azioni, evolve di conseguenza e restituisce all’agente la nuova situazione e la valutazione.

L’interazione procede a passi discreti di tempo $t = 0, 1, 2, \dots$. A ogni passo l’agente osserva lo stato corrente dell’ambiente $S_t \in \mathcal{S}$, la descrizione della situazione in cui deve agire (a scacchi: la configurazione della scacchiera, più eventuali informazioni rilevanti come il tempo rimanente), e sceglie un’azione $A_t \in \mathcal{A}(S_t)$. L’azione ha effetto sull’ambiente, che al passo successivo restituisce un reward numerico $R_{t+1} \in \mathcal{R} \subset \mathbb{R}$, che quantifica l’effetto immediato della decisione, e il nuovo stato $S_{t+1}$. Il ciclo riprende, per sempre oppure fino a una condizione di fine. La storia dell’interazione è quindi una traiettoria

$$S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \dots$$

Per definire formalmente un problema in questo framework servono tre ingredienti:

• Spazio degli stati $\mathcal{S}$: l’insieme di tutte le possibili situazioni dell’ambiente, con le variabili che le descrivono.
• Spazio delle azioni $\mathcal{A}(s)$: l’insieme delle azioni disponibili nello stato $s$. In generale dipende dallo stato: a scacchi non tutte le mosse sono legali in ogni posizione. Quando la dipendenza non è rilevante si scrive semplicemente $\mathcal{A}$.
• Spazio dei reward $\mathcal{R}$: l’insieme dei possibili valori del segnale di reward; può essere tutto $\mathbb{R}$ o un insieme finito di valori.

In parole semplici: l’agente e l’ambiente giocano a un botta e risposta infinito: l’ambiente dice “ecco la situazione”, l’agente risponde “faccio questa mossa”, l’ambiente replica “ecco quanto ti è fruttata e la nuova situazione”. Tutto il reinforcement learning vive dentro questo ciclo.

2. Formalizzare l’ambiente: dalla catena di Markov all’MDP#

2.1 La proprietà di Markov#

Tra tutti i problemi rappresentabili con l’interfaccia agente-ambiente, la teoria si concentra su una famiglia più ristretta e trattabile: quella in cui vale la proprietà di Markov.

A prima vista sembra un’assunzione molto limitante: e se in un problema la storia passata fosse importante? Il punto cruciale è che la proprietà di Markov non va letta come una proprietà del problema, ma come una proprietà della definizione di stato. Se la storia conta, la si può includere nella definizione dello stato: uno stato “arricchito” che contiene le informazioni rilevanti del passato rende di nuovo il processo Markoviano, perché la dipendenza dalla storia è incorporata nello stato stesso. Il prezzo da pagare è uno spazio degli stati più grande e un problema più complesso, ma comunque risolvibile dentro lo stesso framework.

Idea chiave: “Markoviano” significa che lo stato è un riassunto sufficiente del passato: dato lo stato presente, il futuro è indipendente da come ci si è arrivati. Se lo stato scelto non basta, non si cambia teoria: si cambia (allargandola) la definizione di stato.

In parole semplici: lo stato deve contenere tutto ciò che serve per decidere e per prevedere il futuro immediato. Se per giocare bene servisse anche ricordare l’ultima mossa, basta mettere l’ultima mossa dentro lo stato: il processo torna “senza memoria” perché la memoria è stata trasferita nello stato.

2.2 Processi di Markov e Markov Reward Process#

Prima di arrivare all’MDP completo conviene costruire la formalizzazione per gradi, aggiungendo un ingrediente alla volta. Il mattone di base è il processo che descrive solo l’evoluzione casuale degli stati.

Un processo di Markov è un sistema che “vaga” tra gli stati secondo probabilità fisse: non ci sono né decisioni né valutazioni. Il primo arricchimento aggiunge il segnale di reward e il discount factor (il cui ruolo sarà chiarito nella sezione 3).

In un MRP il sistema continua a evolvere da solo, ma ogni visita a uno stato produce un reward: si può quindi chiedere “quanto vale trovarsi in un certo stato”, ma non ancora “che cosa conviene fare”, perché non ci sono azioni. L’MRP è il livello a cui si valuterà una policy fissata: come si vedrà nella sezione 6.4, un MDP in cui il comportamento dell’agente è congelato si riduce esattamente a un MRP.

2.3 Il Processo Decisionale di Markov#

L’ultimo ingrediente è il controllo: l’agente sceglie azioni che influenzano sia le transizioni sia i reward.

Quando vale la proprietà di Markov e gli insiemi di stati e azioni sono finiti, il problema si dice MDP finito; è la classe su cui si concentrerà tutto il resto della trattazione (esistono estensioni a spazi infiniti o continui, ma richiedono strumenti aggiuntivi).

Il modo più compatto di specificare un MDP finito è dare, oltre a $\mathcal{S}$ e $\mathcal{A}$, la cosiddetta dinamica one-step: la distribuzione congiunta del prossimo stato e del reward, condizionata a stato e azione correnti,

$$p(s', r \mid s, a) = \mathbb{P}\left[ S_{t+1} = s', R_{t+1} = r \mid S_t = s, A_t = a \right]$$

È una funzione $p: \mathcal{S} \times \mathcal{R} \times \mathcal{S} \times \mathcal{A} \to [0, 1]$ che soddisfa la condizione di normalizzazione

$$\sum_{s' \in \mathcal{S}} \sum_{r \in \mathcal{R}} p(s', r \mid s, a) = 1 \qquad \forall s \in \mathcal{S},\ \forall a \in \mathcal{A}(s)$$

Grazie alla proprietà di Markov, questa singola distribuzione definisce completamente che cosa succede nel problema: è tutto ciò che c’è da sapere sull’ambiente.

In parole semplici: un MDP è la scheda tecnica completa di un mondo a turni: quali situazioni esistono, quali mosse sono possibili, e per ogni coppia situazione-mossa una tabella di probabilità che dice dove si può finire e con quale premio. Data questa scheda, non serve altro per ragionare sul problema.

2.4 Quantità derivate dalla dinamica one-step#

Dalla dinamica one-step si ricavano per marginalizzazione due quantità che, pur non aggiungendo informazione, sono molto comode nei calcoli:

• la distribuzione del prossimo stato, quando interessa solo dove si finisce e non quanto si guadagna:

$$p(s' \mid s, a) = \sum_{r \in \mathcal{R}} p(s', r \mid s, a)$$

• il reward atteso di una coppia stato-azione, cioè la media dei possibili reward pesata con le rispettive probabilità:

$$r(s, a) = \mathbb{E}\left[ R_{t+1} \mid S_t = s, A_t = a \right] = \sum_{r \in \mathcal{R}} r \sum_{s' \in \mathcal{S}} p(s', r \mid s, a)$$

Entrambe sono già “contenute” nella dinamica one-step; averle come oggetti separati semplifica la scrittura delle equazioni di Bellman.

2.5 Un esempio completo: il robot riciclatore#

Un esempio classico rende concreta la definizione. Un robot mobile raccoglie lattine da riciclare; a ogni passo deve decidere se cercare attivamente lattine, restare fermo aspettando che qualcuno gliene porti, oppure tornare alla base per ricaricarsi. Cercare è più produttivo ma consuma batteria; se la batteria si esaurisce durante la ricerca, il robot resta a terra e qualcuno deve andare a recuperarlo, il che è un esito molto negativo. Le decisioni si basano sul livello di carica, che per semplicità viene modellato con due soli valori. Il reward misura la quantità di lattine raccolte.

Il modello come MDP finito:

• Stati: $\mathcal{S} = \{\text{alta}, \text{bassa}\}$, il livello di carica della batteria.
• Azioni: $\mathcal{A}(\text{alta}) = \{\text{cerca}, \text{attendi}\}$; $\mathcal{A}(\text{bassa}) = \{\text{cerca}, \text{attendi}, \text{ricarica}\}$ (ricaricare con batteria alta non ha senso e viene escluso).
• Reward: $r_{\text{cerca}}$ è il numero atteso di lattine raccolte cercando, $r_{\text{attendi}}$ quello raccolto aspettando, con $r_{\text{cerca}} > r_{\text{attendi}}$; la ricarica non produce lattine (reward 0); il soccorso del robot scarico costa un reward negativo (per esempio $-3$).

La dinamica one-step si descrive con una tabella o, equivalentemente, con un grafo i cui nodi sono gli stati e i cui archi riportano azione, probabilità e reward:

Lettura riga per riga: con carica alta, attendere non consuma batteria (si resta in alta con certezza) e frutta $r_{\text{attendi}}$; cercare frutta di più ma con probabilità $1-\alpha$ fa scendere la carica. Con carica bassa, cercare è rischioso: con probabilità $\beta$ va tutto bene, con probabilità $1-\beta$ la batteria si esaurisce, il robot viene soccorso (reward $-3$) e si ritrova ricaricato in alta. Ricaricare porta con certezza in alta ma non produce nulla, perché il tempo è dedicato alla ricarica e non al riciclo.

I valori numerici ($\alpha$, $\beta$, i reward, il costo del soccorso) possono venire da osservazioni empiriche oppure da scelte di progetto: quantificare con $-3$ il costo del soccorso è una decisione di design che esprime quanto quel fallimento è grave in termini di riciclo perso. Compilata la tabella, la dinamica one-step è completamente definita e con essa l’intero MDP.

In parole semplici: modellare un problema come MDP significa compilare la tabella “se sono in questa situazione e faccio questa mossa, dove finisco, con che probabilità e con che premio”. Il grafo del robot è tutto il suo mondo: da qui in avanti il problema è solo decidere come comportarsi al meglio dentro questo mondo.

3. L’obiettivo dell’agente: return e discount#

3.1 Il return: task episodici e continui#

Come già osservato, l’agente non deve scegliere le azioni sulla base del reward immediato: le conseguenze a lungo termine contano più del guadagno a breve. Serve quindi una quantità che aggreghi l’intera sequenza dei reward futuri.

Sono possibili diverse definizioni di return (reward totale, reward scontato, reward medio); la scelta appropriata dipende dalla struttura temporale del task, che può essere di due tipi.

Task episodici. L’interazione agente-ambiente si spezza naturalmente in blocchi chiamati episodi, ciascuno dei quali termina in uno stato terminale: uno stato oltre il quale non c’è più interazione. Una partita a scacchi è un episodio: prima o poi finisce.

In questo caso la definizione naturale di return è il reward totale fino al passo finale $T$:

$$G_t = R_{t+1} + R_{t+2} + \dots + R_T$$

La somma è finita perché l’episodio termina, e massimizzarne il valore atteso tiene automaticamente conto di tutte le implicazioni a lungo termine delle decisioni prese durante l’episodio.

Task continui. L’interazione prosegue indefinitamente, senza stati terminali: il robot riciclatore, così come è stato modellato, ricicla per sempre. Qui il reward totale è una somma su una sequenza infinita,

$$G_t = R_{t+1} + R_{t+2} + R_{t+3} + \dots$$

e in generale non è finita: anche una strategia mediocre accumula reward all’infinito, e confrontare “infinito con infinito” non permette di distinguere le strategie. La soluzione è scontare i reward futuri con un fattore $\gamma$, con $0 < \gamma < 1$:

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$

L’obiettivo diventa la massimizzazione del return scontato atteso $\mathbb{E}[G_t]$. Se i reward sono limitati in modulo da $R_{\max}$, la serie geometrica garantisce che il return è finito:

$$|G_t| \leq \sum_{k=0}^{\infty} \gamma^k R_{\max} = \frac{R_{\max}}{1 - \gamma}$$

3.2 Il discount factor#

Idea chiave: il discount factor $\gamma$ svolge un doppio ruolo: è un espediente matematico che rende finito il return nei task continui, ed è una manopola di progetto che regola quanto l’agente pesa il futuro rispetto al presente.

Dal punto di vista matematico, qualunque $\gamma$ strettamente minore di 1 funziona: anche $\gamma = 0{,}9999999$ rende la somma convergente. Dal punto di vista del comportamento appreso, però, il valore di $\gamma$ cambia radicalmente le priorità dell’agente:

• con $\gamma = 0$ il return si riduce a $G_t = R_{t+1}$: l’agente è completamente miope e massimizza solo il reward immediato;
• al crescere di $\gamma$ verso 1 l’agente diventa sempre più lungimirante e dà peso crescente ai reward lontani;
• un reward che arriverà tra $k$ passi vale oggi $\gamma^k$ volte il suo valore nominale: i reward molto lontani nel futuro diventano progressivamente irrilevanti, con un orizzonte effettivo dell’ordine di $1/(1-\gamma)$.

In parole semplici: $\gamma$ dice quanto vale un euro promesso domani rispetto a un euro in tasca oggi. Con $\gamma$ piccolo l’agente vive alla giornata; con $\gamma$ vicino a 1 pianifica sul lungo periodo. Oltre a esprimere questa preferenza, $\gamma < 1$ serve tecnicamente a far tornare i conti quando il futuro è infinito.

3.3 Stati assorbenti e notazione unificata#

Avere due definizioni di return, una per i task episodici e una per i continui, è scomodo. C’è un trucco che le unifica. In un task episodico si numera il tempo da zero all’inizio di ogni episodio e si sostituisce lo stato terminale con uno stato assorbente: uno stato da cui non si esce più e in cui ogni transizione produce reward zero. L’episodio, formalmente, non finisce mai: dopo il “vecchio” stato terminale l’interazione continua per sempre, ma senza più accumulare nulla. Il return totale calcolato in questa versione coincide esattamente con quello della versione episodica.

Con questo accorgimento un’unica definizione copre entrambi i casi:

$$G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$$

con le seguenti avvertenze sul valore di $\gamma$:

• $\gamma = 1$ è ammesso solo se uno stato assorbente viene raggiunto con certezza (task episodico): in tal caso la somma è di fatto finita;
• in un task genuinamente continuo si deve usare $\gamma$ strettamente minore di 1;
• $\gamma = 0$ produce un agente che considera solo il reward immediato, mentre $\gamma \to 1$ dà peso sempre maggiore al futuro.

In parole semplici: per non gestire due formule diverse, si finge che ogni episodio finisca in una “stanza senza uscite” dove non succede più niente e non si guadagna più niente. Così anche i problemi con un finale si scrivono come problemi infiniti, e una sola formula del return vale per tutti.

3.4 Goal e reward: l’ipotesi del reward#

Resta da chiedersi se davvero ogni obiettivo si possa esprimere con un segnale di reward. Un principio guida nella progettazione è che un obiettivo deve specificare che cosa si vuole ottenere, non come ottenerlo: il “come” è esattamente ciò che l’agente deve scoprire da solo. Alla base di tutto il framework c’è un’assunzione, tanto potente quanto discussa.

Due schemi standard di progettazione del reward, utili quando si conosce il goal ma non si sa valutare i passi intermedi:

• rappresentazione goal-reward: reward $+1$ (o comunque positivo) al raggiungimento del goal, $0$ in tutti gli altri passi. È una definizione valida ma “avara”: l’agente non riceve alcun indizio fino al goal. Con discount $\gamma < 1$ questo schema premia anche la rapidità, perché un goal raggiunto prima viene scontato meno; con $\gamma = 1$ non c’è invece alcuna pressione a fare in fretta.
• rappresentazione action-penalty: reward $-1$ a ogni passo finché il goal non è raggiunto, $0$ dopo. Qui la pressione temporale è incorporata: ogni passo in più costa, quindi conviene arrivare al goal il prima possibile, anche con $\gamma = 1$.

L’ipotesi del reward non è priva di sfide. Due scenari notoriamente difficili da catturare con un segnale scalare: i comportamenti sensibili al rischio (un agente di trading deve bilanciare guadagno atteso e rischio di perdita, non solo massimizzare il primo) e la diversità di comportamento (in un videogioco, un’intelligenza artificiale che gioca sempre la stessa strategia ottima può essere meno desiderabile di una variata). In linea di principio anche questi aspetti si possono codificare estendendo la funzione di reward, ma la progettazione diventa complessa.

In parole semplici: l’ipotesi del reward scommette che qualunque scopo si possa tradurre in un punteggio da massimizzare. Spesso funziona benissimo, con ricette semplici come “1 al traguardo, 0 altrove” oppure “-1 a ogni passo finché non arrivi”; per obiettivi sfumati come “guadagna ma senza rischiare troppo” la traduzione in punteggio è possibile ma tutt’altro che banale.

4. La policy#

4.1 Policy deterministiche e stocastiche#

Definito l’obiettivo (massimizzare il return atteso), resta da specificare l’oggetto che l’agente deve apprendere: la strategia di comportamento.

Le policy si classificano lungo tre assi: Markoviane o non Markoviane, deterministiche o stocastiche, stazionarie o non stazionarie.

Nel caso più semplice la policy è deterministica: una funzione

$$\pi: \mathcal{S} \to \mathcal{A}, \qquad a = \pi(s)$$

che mappa ogni stato in un’azione. In un MDP finito una policy deterministica non è altro che una tabella con una riga per stato: nello stato $s_0$ esegui $a_1$, nello stato $s_1$ esegui $a_0$, e così via. Nella rappresentazione grafica di un gridworld (un ambiente a griglia in cui l’agente si muove di cella in cella) una policy deterministica si disegna mettendo in ogni cella la freccia dell’azione prescritta.

Il caso più generale è la policy stocastica: una funzione che mappa ogni stato in una distribuzione di probabilità sulle azioni,

$$\pi(a \mid s) = \mathbb{P}\left[ A_t = a \mid S_t = s \right], \qquad \sum_{a \in \mathcal{A}(s)} \pi(a \mid s) = 1, \quad \pi(a \mid s) \geq 0$$

In forma tabellare: una riga per stato, una colonna per azione, e in ogni casella la probabilità di scegliere quell’azione in quello stato (ogni riga somma a 1). La rappresentazione stocastica include quella deterministica come caso particolare: basta una riga con un 1 sull’azione prescritta e 0 altrove. Per questo motivo si userà spesso la notazione stocastica $\pi(a \mid s)$ per generalità, anche quando la policy in gioco è deterministica.

In parole semplici: la policy è il “manuale di comportamento” dell’agente: per ogni situazione dice che cosa fare, o con quali probabilità scegliere tra le mosse. Imparare, in un MDP, significa esattamente costruire questo manuale.

4.2 Policy Markoviane e stazionarie#

Una policy si dice Markoviana se la scelta dell’azione dipende soltanto dallo stato corrente, e non Markoviana se dipende anche dalla storia passata. Un esempio minimale chiarisce la distinzione. Si consideri un MDP con un solo stato e due azioni, destra (R) e sinistra (L), e due policy:

• $\pi_1$: scegli R il 50% delle volte e L il 50% delle volte;
• $\pi_2$: alterna R e L (una volta R, la volta dopo L, e così via).

$\pi_1$ è Markoviana: per decidere bastano lo stato corrente (che qui è sempre lo stesso) e un lancio di moneta. $\pi_2$ non lo è: per decidere serve ricordare l’ultima azione eseguita, informazione non contenuta nello stato; quindi non è una policy valida per questo MDP. La limitazione si supera con lo stesso trucco visto per la proprietà di Markov: si estende la definizione di stato includendovi l’azione precedente. Nel nuovo MDP, con due stati (“l’ultima azione era R” / “era L”), la policy che alterna diventa Markoviana. L’essere Markoviana non è quindi una proprietà assoluta di una policy, ma è relativa all’MDP su cui la si definisce.

Una policy si dice inoltre stazionaria se non cambia nel tempo: la regola di decisione al passo $t = 5$ è la stessa del passo $t = 5000$. Una policy non stazionaria può invece dipendere esplicitamente dal tempo.

Nel seguito la trattazione si concentra su policy Markoviane e stazionarie. La restrizione a policy deterministiche o stocastiche è invece lasciata aperta: come si vedrà nella sezione 7.2, negli MDP il framework garantisce che esiste sempre una policy ottima deterministica, quindi ai fini dell’ottimalità ci si potrà limitare alle deterministiche senza perdita.

In parole semplici: una policy Markoviana guarda solo la fotografia del presente, mai l’album dei ricordi. Se una strategia utile ha bisogno di ricordi, si allarga la definizione di stato finché i ricordi necessari non ci stanno dentro; a quel punto la strategia torna a dipendere solo dallo stato.

5. Quanto vale uno stato: le value function#

5.1 State-value function e action-value function#

Fissata una policy $\pi$, il comportamento dell’agente è completamente determinato (in senso probabilistico), e si può chiedere quanto “renda” ciascuno stato seguendo quella policy.

La differenza è sottile ma importante: $V^{\pi}(s)$ valuta lo stato assumendo che anche la prima azione sia scelta da $\pi$; $Q^{\pi}(s, a)$ valuta “che cosa succede se in $s$ eseguo $a$ (anche se $\pi$ avrebbe fatto altro) e solo dopo torno a seguire $\pi$”. Le due funzioni sono legate dalla relazione

$$V^{\pi}(s) = \sum_{a \in \mathcal{A}(s)} \pi(a \mid s) \, Q^{\pi}(s, a)$$

il valore di uno stato è la media dei valori delle azioni disponibili, pesata con le probabilità con cui $\pi$ le sceglie. La $Q$ sarà lo strumento chiave per migliorare una policy: confrontare $Q^{\pi}(s, a)$ al variare di $a$ dice se in $s$ esiste un’azione migliore di quella che $\pi$ sta usando.

In parole semplici: $V^{\pi}(s)$ risponde a “quanto mi aspetto di guadagnare, in totale e scontato, se mi trovo qui e continuo con la mia strategia?”; $Q^{\pi}(s,a)$ risponde a “e se qui, per una volta, facessi quest’altra mossa e poi tornassi alla mia strategia?”. La seconda domanda è quella che permette di scoprire strategie migliori.

5.2 Perché servono le value function: due esempi#

Scacchi e delayed reward. Si definisca il reward come $+1$ se il bianco vince e $0$ in ogni altro caso. Durante la partita quasi ogni mossa produce reward immediato $R_t = 0$: il segnale utile arriva solo alla fine. In questo setting $V^{\pi}(s)$ ha un’interpretazione limpida: è la probabilità che il bianco vinca partendo dalla posizione $s$ e giocando secondo $\pi$.

Due mosse con lo stesso reward immediato (zero) possono portare in posizioni con valori diversi, per esempio $V^{\pi} = 0{,}51$ contro $V^{\pi} = 0{,}49$: la value function condensa tutto il futuro in un numero disponibile adesso, ed è per questo lo strumento che risolve il problema del delayed reward.

Idea chiave: la value function trasforma un problema di conseguenze lontane in un problema di confronti immediati: invece di aspettare la fine dell’episodio per sapere se una mossa era buona, si guarda il valore dello stato in cui la mossa conduce.

Un gridworld con teletrasporti. Si consideri una griglia $5 \times 5$ in cui l’agente si muove con quattro azioni deterministiche (nord, sud, est, ovest). I reward: $-1$ se l’azione porta a sbattere contro il bordo (l’agente resta fermo), $0$ per i movimenti normali, con due celle speciali: dalla cella $A$ ogni azione frutta $+10$ e teletrasporta in una cella $A'$ vicina al bordo inferiore; dalla cella $B$ ogni azione frutta $+5$ e teletrasporta in una cella $B'$ a metà griglia. La policy da valutare è quella casuale uniforme (25% a ciascuna direzione), con $\gamma = 0{,}9$.

Dal calcolo di $V^{\pi}$ emergono due fatti istruttivi:

• $V^{\pi}(A) \approx 8{,}8$, meno del reward immediato $+10$: da $A$ si guadagna subito $10$, ma si atterra in $A'$, vicino al bordo inferiore, dove la policy casuale sbatterà spesso contro le pareti accumulando reward negativi scontati; il valore incorpora anche questo futuro sfavorevole;
• $V^{\pi}(B) \approx 5{,}3$, più del reward immediato $+5$: da $B'$, ben posizionata al centro, il futuro atteso è positivo, perché è probabile ripassare da $A$ o da $B$.

Questo esempio mostra che il valore di uno stato non coincide con ciò che lo stato paga subito: è il bilancio complessivo di presente e futuro scontato.

In parole semplici: una cella che regala molto ma ti scaraventa in una zona pericolosa vale meno di quanto regala; una cella che regala poco ma ti piazza in una buona posizione vale più di quanto regala. La value function fa questi conti per ogni stato.

6. Le equazioni di Bellman di aspettativa#

6.1 La decomposizione ricorsiva del return#

Il calcolo diretto di $V^{\pi}$ dalla definizione richiederebbe di mediare su tutte le possibili traiettorie infinite: impraticabile. La chiave di volta è un’osservazione elementare sulla struttura del return: raccogliendo $\gamma$ a fattore comune da tutti i termini successivi al primo,

$$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots = R_{t+1} + \gamma \left( R_{t+2} + \gamma R_{t+3} + \dots \right) = R_{t+1} + \gamma \, G_{t+1}$$

Il return da oggi è il reward immediato più il return da domani, scontato di $\gamma$. Questa ricorsione a un passo è il cuore di tutta la teoria (e di quasi tutti gli algoritmi che seguiranno nel corso).

Idea chiave: il valore di adesso si decompone in “quello che incasso subito” più “$\gamma$ volte il valore di dove finisco”. Applicando questa decomposizione dentro il valore atteso, le value function smettono di essere medie su traiettorie infinite e diventano soluzioni di un sistema di equazioni a un passo.

6.2 Le equazioni per V e Q#

Prendendo il valore atteso della decomposizione, condizionato a $S_t = s$ e sotto la policy $\pi$, e usando la proprietà di Markov (il valore atteso di $G_{t+1}$ dato $S_{t+1} = s'$ è esattamente $V^{\pi}(s')$), si ottiene la prima equazione di Bellman.

Lettura da fuori a dentro: si media sulle azioni che $\pi$ può scegliere in $s$; per ciascuna azione si media sulle coppie (prossimo stato, reward) secondo la dinamica one-step; per ogni esito si somma il reward immediato $r$ al valore scontato dello stato d’arrivo. Con le quantità derivate della sezione 2.4 la stessa equazione si scrive in modo più compatto:

$$V^{\pi}(s) = \sum_{a} \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V^{\pi}(s') \right]$$

La action-value function si decompone in modo del tutto analogo: fissata la prima azione, si media sugli esiti e poi sull’azione successiva scelta da $\pi$.

Le due equazioni si intrecciano attraverso le relazioni a mezzo passo, che conviene tenere a portata di mano:

$$V^{\pi}(s) = \sum_{a} \pi(a \mid s) \, Q^{\pi}(s, a), \qquad Q^{\pi}(s, a) = r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V^{\pi}(s')$$

Il punto fondamentale: in un MDP finito con $|\mathcal{S}|$ stati, l’equazione di Bellman per $V^{\pi}$ è un sistema di $|\mathcal{S}|$ equazioni lineari in $|\mathcal{S}|$ incognite (i valori $V^{\pi}(s)$). Le incognite compaiono solo al primo grado: valutare una policy è algebra lineare.

In parole semplici: l’equazione di Bellman dice che il valore di ogni stato è coerente con i valori dei suoi vicini: valore di qui = premio immediato medio + $\gamma$ volte il valore medio di dove si finisce. Scrivendo questa condizione per tutti gli stati si ottiene un normale sistema lineare, con un’equazione e un’incognita per stato.

6.3 Esempio concreto: un gridworld a quattro stati#

Vediamo le equazioni di Bellman all’opera su un esempio piccolo ma completo, tratto dalle slide del corso. L’ambiente è una griglia $2 \times 2$ con stati $A$ (in alto a sinistra), $B$ (in alto a destra), $C$ (in basso a sinistra) e $D$ (in basso a destra). Le quattro azioni (su, giù, sinistra, destra) sono deterministiche; un’azione che porterebbe fuori dalla griglia lascia l’agente dove si trova. Ogni transizione che entra in $B$, anche “sbattendo” e restando in $B$, produce reward $+5$; ogni altra transizione produce $0$. La policy da valutare è quella casuale uniforme ($25\%$ per direzione) con $\gamma = 0{,}7$. Scrivendo l’equazione di aspettativa di Bellman in ciascuno dei quattro stati (per esempio da $A$: con probabilità $1/4$ si va a destra in $B$ incassando $5$, con $1/4$ si scende in $C$, con $1/2$ si sbatte e si resta in $A$):

$$V^{\pi}(A) = \tfrac{1}{4}\left(5 + 0{,}7\,V^{\pi}(B)\right) + \tfrac{1}{4}\,0{,}7\,V^{\pi}(C) + \tfrac{1}{2}\,0{,}7\,V^{\pi}(A)$$

$$V^{\pi}(B) = \tfrac{1}{2}\left(5 + 0{,}7\,V^{\pi}(B)\right) + \tfrac{1}{4}\,0{,}7\,V^{\pi}(A) + \tfrac{1}{4}\,0{,}7\,V^{\pi}(D)$$

$$V^{\pi}(C) = \tfrac{1}{4}\,0{,}7\,V^{\pi}(A) + \tfrac{1}{4}\,0{,}7\,V^{\pi}(D) + \tfrac{1}{2}\,0{,}7\,V^{\pi}(C)$$

$$V^{\pi}(D) = \tfrac{1}{4}\left(5 + 0{,}7\,V^{\pi}(B)\right) + \tfrac{1}{4}\,0{,}7\,V^{\pi}(C) + \tfrac{1}{2}\,0{,}7\,V^{\pi}(D)$$

Quattro equazioni lineari in quattro incognite: risolvendo il sistema si ottiene

$$V^{\pi}(A) \approx 4{,}2, \qquad V^{\pi}(B) \approx 6{,}1, \qquad V^{\pi}(C) \approx 2{,}2, \qquad V^{\pi}(D) \approx 4{,}2$$

I numeri raccontano la geografia del problema: $B$ vale di più perché metà delle mosse da $B$ incassano di nuovo $+5$; $A$ e $D$ hanno lo stesso valore per simmetria (entrambe confinano con $B$ e con $C$); $C$, l’angolo più lontano dalla cella premiante, vale meno di tutte.

I passaggi della soluzione

Si indichino i quattro valori con $a, b, c, d$. Le equazioni di $A$ e di $D$ hanno la stessa identica forma, quindi $a = d$ (simmetria della griglia rispetto alla diagonale $B$-$C$). L’equazione di $C$ dà

$$c = 0{,}175\,(a + d) + 0{,}35\,c \;\Longrightarrow\; 0{,}65\,c = 0{,}35\,a \;\Longrightarrow\; c \approx 0{,}538\,a$$

L’equazione di $B$ dà $0{,}65\,b = 2{,}5 + 0{,}175\,(a + d) = 2{,}5 + 0{,}35\,a$, cioè $b \approx 3{,}846 + 0{,}538\,a$. Sostituendo $b$ e $c$ nell’equazione di $A$:

$$0{,}65\,a = 1{,}25 + 0{,}175\,b + 0{,}175\,c \;\Longrightarrow\; 0{,}4615\,a \approx 1{,}923 \;\Longrightarrow\; a \approx 4{,}17$$

da cui $b \approx 6{,}09$, $c \approx 2{,}24$, $d = a \approx 4{,}17$: arrotondando, i valori $4{,}2$, $6{,}1$, $2{,}2$, $4{,}2$ della slide.

6.4 Forma matriciale e soluzione in forma chiusa#

Una volta fissata la policy $\pi$, le azioni non sono più una scelta libera: vengono estratte da $\pi(\cdot \mid s)$. L’MDP, visto dall’esterno, si comporta allora come un MRP con dinamica e reward “mediati” dalla policy:

$$P^{\pi}_{ss'} = \sum_{a} \pi(a \mid s) \, p(s' \mid s, a), \qquad R^{\pi}(s) = \sum_{a} \pi(a \mid s) \, r(s, a)$$

Raccogliendo i valori in un vettore $V^{\pi} \in \mathbb{R}^{|\mathcal{S}|}$ (una componente per stato) e i reward attesi in un vettore $R^{\pi}$, l’equazione di Bellman diventa un’unica equazione vettoriale:

$$V^{\pi} = R^{\pi} + \gamma P^{\pi} V^{\pi}$$

Portando le incognite a sinistra e risolvendo:

$$\left( I - \gamma P^{\pi} \right) V^{\pi} = R^{\pi} \quad \Longrightarrow \quad V^{\pi} = \left( I - \gamma P^{\pi} \right)^{-1} R^{\pi}$$

L’inversa esiste sempre per $\gamma < 1$: $P^{\pi}$ è una matrice stocastica (righe non negative che sommano a 1), i suoi autovalori hanno modulo al più 1, quindi gli autovalori di $I - \gamma P^{\pi}$ hanno tutti modulo positivo e la matrice è non singolare. La policy evaluation, cioè il calcolo di $V^{\pi}$ data una policy, ammette dunque una soluzione esatta in forma chiusa, esattamente come l’OLS nella regressione lineare.

In parole semplici: valutare una policy è “solo” risolvere un sistema lineare: si costruiscono la matrice delle transizioni medie e il vettore dei premi medi indotti dalla policy, e una formula chiusa restituisce il valore di tutti gli stati in un colpo solo.

6.5 L’operatore di Bellman e la proprietà di contrazione#

La struttura dell’equazione di Bellman si presta a una lettura più astratta che sarà preziosa per gli algoritmi iterativi. Si definisce l’operatore di Bellman di aspettativa $T^{\pi}$, che prende una funzione di valore qualsiasi $V$ (un vettore di $\mathbb{R}^{|\mathcal{S}|}$) e restituisce la funzione ottenuta applicando un passo di backup:

$$\left( T^{\pi} V \right)(s) = \sum_{a} \pi(a \mid s) \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V(s') \right]$$

ossia, in forma vettoriale, $T^{\pi} V = R^{\pi} + \gamma P^{\pi} V$. Per costruzione, $V^{\pi}$ è un punto fisso di $T^{\pi}$: applicare l’operatore a $V^{\pi}$ restituisce $V^{\pi}$ stesso, perché è proprio quanto afferma l’equazione di Bellman. La proprietà decisiva è la seguente.

La verifica è breve: per ogni stato $s$,

$$\left| (T^{\pi} V_1)(s) - (T^{\pi} V_2)(s) \right| = \gamma \left| \sum_{s'} P^{\pi}_{ss'} \left( V_1(s') - V_2(s') \right) \right| \leq \gamma \sum_{s'} P^{\pi}_{ss'} \left| V_1(s') - V_2(s') \right| \leq \gamma \left\lVert V_1 - V_2 \right\rVert_{\infty}$$

dove l’ultimo passaggio usa il fatto che le $P^{\pi}_{ss'}$ sommano a 1. I termini di reward si cancellano nella differenza: la contrazione agisce solo sulla parte “futura”, ed è lì che entra il fattore $\gamma$.

Le conseguenze, via teorema del punto fisso di Banach, sono due e valgono entrambe per $\gamma < 1$:

• il punto fisso di $T^{\pi}$ è unico: $V^{\pi}$ è l’unica soluzione dell’equazione di Bellman;
• l’applicazione iterata di $T^{\pi}$ a partire da una funzione di valore qualsiasi converge a $V^{\pi}$, e l’errore si riduce almeno di un fattore $\gamma$ a ogni applicazione: $\lVert T^{\pi} V - V^{\pi} \rVert_{\infty} \leq \gamma \lVert V - V^{\pi} \rVert_{\infty}$.

Questa seconda proprietà è il fondamento della iterative policy evaluation: invece di invertire una matrice si parte da $V = 0$ (o da qualunque stima) e si applica ripetutamente il backup di Bellman finché i valori non si stabilizzano.

In parole semplici: l’operatore di Bellman è una “centrifuga” che, applicata a una stima qualsiasi dei valori, la avvicina sempre alla soluzione vera, riducendo l’errore di un fattore $\gamma$ a ogni giro. Girare la centrifuga abbastanza volte porta alla soluzione con la precisione desiderata, senza invertire alcuna matrice.

6.6 I limiti della soluzione esatta#

Perché servono le versioni iterative se esiste la forma chiusa? Per una questione di scala. Risolvere il sistema lineare costa $O(|\mathcal{S}|^3)$: con i 4 stati dell’esempio del gridworld si risolvono 4 equazioni a mano; con gli scacchi, dove il numero di stati è dell’ordine di $10^{44}$, bisognerebbe risolvere $10^{44}$ equazioni lineari, fuori discussione per qualunque calcolatore presente o futuro. Il problema non è concettuale ma computazionale, e diventa ancora più grave quando, come accadrà nel reinforcement learning vero e proprio, la dinamica $p$ non è nemmeno nota. Le equazioni di Bellman restano comunque il fondamento: tutti gli algoritmi dei prossimi capitoli sono modi più o meno diretti di risolverle in maniera approssimata o incrementale.

7. Che cosa significa “ottimo”: ordinamento e policy ottima#

7.1 L’ordinamento parziale delle policy#

Le value function forniscono il criterio naturale per confrontare le policy tra loro.

Il requisito “per ogni stato” è forte, e rende l’ordinamento parziale: due policy possono essere incomparabili, per esempio se la prima è migliore negli stati di una zona dell’ambiente e la seconda è migliore altrove. Non è quindi ovvio, a priori, che esista una policy “migliore di tutte”: potrebbe esserci solo un mosaico di policy ciascuna imbattibile nella propria zona.

7.2 Esistenza di una policy ottima deterministica#

Il risultato centrale della teoria degli MDP è che il timore del “mosaico di policy incomparabili” è infondato.

Lo schema della dimostrazione (nel caso finito) si basa su una costruzione per combinazione. Si prendano due policy qualsiasi $\pi_1$ e $\pi_2$, eventualmente incomparabili, e si costruisca una terza policy $\pi_3$ che in ogni stato imita la migliore delle due in quello stato:

$$\pi_3(s) = \begin{cases} \pi_1(s) & \text{se } V^{\pi_1}(s) \geq V^{\pi_2}(s) \\ \pi_2(s) & \text{altrimenti} \end{cases}$$

Si dimostra che $\pi_3$ è almeno buona quanto entrambe in tutti gli stati: $V^{\pi_3}(s) \geq \max\left( V^{\pi_1}(s), V^{\pi_2}(s) \right)$ per ogni $s$. L’intuizione: seguendo $\pi_3$, in ogni stato si agisce come la policy localmente migliore, e la stessa regola si applicherà anche negli stati futuri; il valore raccolto non può quindi essere inferiore a quello della migliore delle due policy di partenza. Due policy incomparabili si possono dunque sempre “fondere” in una che le domina entrambe; poiché in un MDP finito le policy deterministiche Markoviane sono in numero finito, iterando la combinazione si arriva a una policy che domina ogni altra: la policy ottima. La costruzione produce naturalmente una policy deterministica: in ogni stato viene selezionata una specifica azione. La stocasticità può servire ad altri scopi (per esempio a esplorare durante l’apprendimento), ma non serve per essere ottimi in un MDP.

Idea chiave: negli MDP le policy migliori “in zone diverse” non si escludono a vicenda: si combinano stato per stato in una policy che eredita il meglio di ciascuna. Ripetendo la fusione, l’ordinamento parziale rivela un massimo globale, e questo massimo si può sempre realizzare con una policy deterministica.

In parole semplici: esiste sempre un manuale di comportamento perfetto, che in ogni situazione prescrive una singola mossa (niente lanci di moneta) ed è imbattibile ovunque, non solo in media. Il motivo è che si può sempre costruire “il meglio dei due mondi”: dove una strategia è più forte si copia lei, dove è più forte l’altra si copia l’altra.

7.3 Esempio concreto: la policy ottima dipende da gamma#

Un piccolo MDP tratto dalle slide mostra un aspetto spesso trascurato: la policy ottima è ottima per un dato $\gamma$, perché il discount factor fa parte della definizione del problema.

Nello stato $X$ sono disponibili due azioni: $A_1$ porta in $Y$ con reward $+1$, $A_2$ porta in $Z$ con reward $0$. Da $Y$ e da $Z$ c’è un’unica azione, che riporta in $X$: con reward $0$ da $Y$, con reward $+2$ da $Z$. Le policy deterministiche distinte sono quindi solo due: $\pi_1(X) = A_1$ (incassa $+1$ subito) e $\pi_2(X) = A_2$ (rinuncia al reward immediato per il $+2$ al passo dopo).

Con $\gamma = 0$ conta solo il reward immediato:

$$V^{\pi_1}(X) = 1, \qquad V^{\pi_2}(X) = 0 \qquad \Longrightarrow \qquad \pi_1 \text{ è ottima}$$

Con $\gamma = 0{,}9$ i reward arrivano alternati (uno ogni due passi) e le serie geometriche danno il verdetto opposto:

$$V^{\pi_1}(X) = \sum_{k=0}^{\infty} (0{,}9)^{2k} = \frac{1}{1 - 0{,}81} \approx 5{,}3, \qquad V^{\pi_2}(X) = \sum_{k=0}^{\infty} (0{,}9)^{2k+1} \cdot 2 = \frac{0{,}9 \cdot 2}{1 - 0{,}81} \approx 9{,}5$$

quindi con $\gamma = 0{,}9$ è ottima $\pi_2$: la pazienza paga, ma solo se l’agente è abbastanza lungimirante da apprezzarla. Si noti che il teorema di esistenza non è contraddetto: per ogni valore fissato di $\gamma$ esiste una policy ottima deterministica; semplicemente, cambiando $\gamma$ cambia il problema e con esso la sua soluzione.

7.4 La ricerca esaustiva e i suoi limiti#

Il teorema di esistenza suggerisce un algoritmo concettualmente banale per trovare $\pi^{*}$: enumerare tutte le policy deterministiche, valutare ciascuna con la forma chiusa della sezione 6.4 e scegliere la dominante. Il problema è il conteggio: con $|\mathcal{S}|$ stati e $|\mathcal{A}|$ azioni per stato, le policy deterministiche sono

$$|\mathcal{A}|^{|\mathcal{S}|}$$

perché per ogni stato si sceglie indipendentemente una delle azioni. Nell’esempio del bivio le policy sono 2 e la ricerca brute-force è praticabile; ma il numero esplode in fretta: un modesto gridworld $5 \times 5$ con 4 azioni ha $4^{25} \approx 10^{15}$ policy deterministiche, ciascuna con il suo sistema lineare da risolvere. La ricerca esaustiva è quindi inutilizzabile su qualunque problema non giocattolo, e serve una via più intelligente: passare per le equazioni di ottimalità.

8. Le value function ottime e le equazioni di ottimalità#

8.1 Value function ottime#

Anche senza costruire esplicitamente una policy dominante, si possono definire i valori migliori raggiungibili stato per stato.

$V^{*}(s)$ è il miglior return atteso ottenibile da $s$ da qualunque comportamento; $Q^{*}(s, a)$ è il miglior return atteso ottenibile eseguendo $a$ in $s$ e comportandosi al meglio da lì in poi. Per il teorema di esistenza, questi massimi sono realizzati simultaneamente dalla policy ottima: $V^{\pi^{*}} = V^{*}$ e $Q^{\pi^{*}} = Q^{*}$. Conoscere $V^{*}$ significa sapere quanto “rende al massimo” il problema; come si vedrà tra poco, conoscere $Q^{*}$ significa molto di più: significa saper giocare in modo ottimo.

8.2 Le equazioni di ottimalità di Bellman#

Le value function ottime soddisfano versioni speciali delle equazioni di Bellman, in cui la media sulle azioni della policy è sostituita da una massimizzazione. Il ragionamento parte dalla relazione tra $V^{*}$ e $Q^{*}$. Una policy ottima, in ogni stato, deve scegliere un’azione che realizza il miglior valore possibile: se scegliesse un’azione con $Q^{*}$ inferiore al massimo, si potrebbe migliorarla, contraddicendone l’ottimalità. Quindi

$$V^{*}(s) = \max_{a \in \mathcal{A}(s)} Q^{*}(s, a)$$

D’altra parte, il valore ottimo di una coppia stato-azione si decompone come sempre in reward immediato più futuro scontato, e il futuro, per definizione di ottimalità, vale $V^{*}$:

$$Q^{*}(s, a) = r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V^{*}(s')$$

Sostituendo ciascuna relazione nell’altra si ottengono le due equazioni chiuse.

La differenza rispetto alle equazioni di aspettativa è tutta in un simbolo: dove prima c’era la media pesata $\sum_a \pi(a \mid s) (\cdot)$ ora c’è $\max_a (\cdot)$. La media descrive una policy data; il massimo descrive la policy migliore possibile, senza doverla nominare.

In parole semplici: l’equazione di ottimalità dice che il valore ottimo di uno stato è quello ottenibile giocando la mossa migliore, dove “migliore” tiene già conto che anche in futuro si giocherà sempre la mossa migliore. È la stessa ricorsione di Bellman, con “faccio quello che dice la policy” sostituito da “faccio la cosa migliore”.

8.3 Dalla value function ottima alla policy ottima#

Perché queste equazioni sono così importanti? Perché da $V^{*}$ o $Q^{*}$ la policy ottima si ricava immediatamente, senza ulteriore apprendimento: basta agire in modo greedy, cioè scegliere in ogni stato l’azione che massimizza il valore.

• Con $Q^{*}$ la ricetta è diretta e non richiede nemmeno di conoscere la dinamica dell’ambiente:

$$\pi^{*}(s) = \arg\max_{a \in \mathcal{A}(s)} Q^{*}(s, a)$$

• Con $V^{*}$ serve un lookahead a un passo attraverso il modello: si valuta ogni azione combinando reward immediato e valore ottimo scontato degli stati raggiungibili,

$$\pi^{*}(s) = \arg\max_{a \in \mathcal{A}(s)} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V^{*}(s') \right]$$

Un mini esempio con $\gamma = 1$ mostra che “greedy rispetto ai valori ottimi” non significa “miope”. In uno stato $s$ ci sono due azioni: $a_1$ dà reward immediato $2$ e porta con certezza in uno stato con $V^{*} = 3$; $a_2$ dà reward immediato $5$ e porta in uno stato con $V^{*} = -1$. Allora

$$Q^{*}(s, a_1) = 2 + 3 = 5, \qquad Q^{*}(s, a_2) = 5 - 1 = 4$$

e la scelta ottima è $a_1$, nonostante il suo reward immediato sia meno della metà di quello di $a_2$: il valore dello stato d’arrivo incorpora già tutte le conseguenze future, quindi la scelta localmente greedy sul $Q^{*}$ è globalmente ottima.

Sul gridworld con i teletrasporti l’intero percorso si chiude visivamente: calcolata $V^{*}$, la policy ottima si legge cella per cella scegliendo la direzione che porta al vicino di valore massimo.

Idea chiave: conoscere $Q^{*}$ risolve il problema: la policy ottima è la scelta greedy $\pi^{*}(s) = \arg\max_a Q^{*}(s,a)$. Tutta la difficoltà del controllo ottimo si trasferisce così dal cercare la policy al calcolare la value function ottima.

In parole semplici: se qualcuno regalasse la tabella $Q^{*}$, giocare in modo perfetto sarebbe banale: in ogni situazione si legge la riga dello stato e si sceglie la casella col numero più grande. Il difficile non è usare $Q^{*}$: è procurarselo.

8.4 Perché non esiste una soluzione in forma chiusa#

Per la policy evaluation la pipeline era: dati $r$, $p$ e $\gamma$, si costruisce un sistema lineare e un solutore lo risolve esattamente. Verrebbe naturale replicare lo schema per $V^{*}$: dati $r$, $p$ e $\gamma$, risolvere le equazioni di ottimalità. Ma qui la pipeline si inceppa: l’operatore $\max$ non è lineare, quindi le equazioni di ottimalità di Bellman formano un sistema di $|\mathcal{S}|$ equazioni non lineari in $|\mathcal{S}|$ incognite, e in generale non ammettono soluzione in forma chiusa.

C’è anche una circolarità istruttiva: se si conoscesse la policy ottima $\pi^{*}$, il calcolo di $V^{*} = V^{\pi^{*}}$ tornerebbe a essere un sistema lineare (basterebbe la policy evaluation con $\pi^{*}$, $r$, $p$, $\gamma$); ma per conoscere $\pi^{*}$ serve $V^{*}$ (o $Q^{*}$), che è proprio l’incognita. Serve un metodo che rompa il circolo.

La buona notizia è che la struttura di contrazione sopravvive al passaggio al massimo. Definendo l’operatore di ottimalità di Bellman

$$\left( T^{*} V \right)(s) = \max_{a \in \mathcal{A}(s)} \left[ r(s, a) + \gamma \sum_{s'} p(s' \mid s, a) \, V(s') \right]$$

si dimostra che anche $T^{*}$ è una $\gamma$-contrazione in norma del massimo (la dimostrazione ricalca quella di $T^{\pi}$ nella sezione 6.5, con in più una disuguaglianza sulla differenza di massimi: $|\max_a f(a) - \max_a g(a)| \leq \max_a |f(a) - g(a)|$). Ne segue che $V^{*}$ è l’unico punto fisso di $T^{*}$ e che l’applicazione iterata di $T^{*}$ da qualunque inizializzazione converge a $V^{*}$. Questa è la giustificazione teorica dei metodi iterativi che occuperanno i prossimi capitoli:

• gli algoritmi di programmazione dinamica (policy iteration, value iteration), che risolvono le equazioni di Bellman iterativamente assumendo di conoscere il modello ($r$ e $p$);
• gli algoritmi di reinforcement learning propriamente detti, che risolvono le stesse equazioni quando il modello è ignoto, sostituendo le aspettative con campioni di esperienza raccolti interagendo con l’ambiente.

In parole semplici: con il “max” di mezzo il sistema non si risolve più con una formula, e non si può nemmeno aggirare l’ostacolo dicendo “prima trovo la policy ottima e poi risolvo il sistema lineare”, perché per trovarla servirebbe già la soluzione. Se ne esce iterando: la versione col massimo dell’operatore di Bellman è ancora una contrazione, quindi applicarla ripetutamente porta comunque ai valori ottimi. Tutti gli algoritmi dei prossimi capitoli sono varianti di questa idea.

9. Esempio svolto: il robot riciclatore#

Per consolidare l’intero percorso, si risolve completamente una versione numerica del robot riciclatore della sezione 2.5: valutazione di alcune policy, confronto, e verifica di ottimalità tramite le equazioni di Bellman.

9.1 Il modello con valori numerici#

Si fissano i parametri: $\alpha = 0{,}9$, $\beta = 0{,}6$, $r_{\text{cerca}} = 2$, $r_{\text{attendi}} = 1$, penalità di soccorso $-3$, discount $\gamma = 0{,}9$. Gli stati sono $\{A, B\}$ (carica alta e bassa), con azioni $\mathcal{A}(A) = \{\text{cerca}, \text{attendi}\}$ e $\mathcal{A}(B) = \{\text{cerca}, \text{attendi}, \text{ricarica}\}$. Le policy deterministiche possibili sono $2 \times 3 = 6$: su un problema così piccolo la ricerca esaustiva sarebbe fattibile, ma si seguirà la strada delle equazioni di Bellman, che è quella che scala.

9.2 Riscaldamento: la policy “attendi sempre”#

Sia $\pi_0$ la policy che attende in entrambi gli stati. Attendere lascia lo stato invariato con certezza e frutta sempre $1$, quindi l’equazione di Bellman in ciascuno stato è

$$V^{\pi_0}(s) = 1 + \gamma \, V^{\pi_0}(s) \quad \Longrightarrow \quad V^{\pi_0}(s) = \frac{1}{1 - \gamma} = \frac{1}{0{,}1} = 10$$

per entrambi gli stati. È la serie geometrica dei reward costanti: un reward di $1$ a ogni passo, scontato con $\gamma = 0{,}9$, vale complessivamente $10$. Questo numero fa da riferimento per le policy più intraprendenti.

9.3 Valutazione della policy prudente#

Sia $\pi_1$ la policy: cerca quando la carica è alta, ricarica quando è bassa. Le equazioni di Bellman (un’equazione per stato, usando la tabella della dinamica):

$$V^{\pi_1}(A) = 2 + 0{,}9 \left[ 0{,}9 \, V^{\pi_1}(A) + 0{,}1 \, V^{\pi_1}(B) \right]$$

$$V^{\pi_1}(B) = 0 + 0{,}9 \, V^{\pi_1}(A)$$

La prima dice: cercando da $A$ si incassa $2$ e si resta in $A$ con probabilità $0{,}9$ o si scende in $B$ con probabilità $0{,}1$. La seconda: ricaricando da $B$ non si incassa nulla e si torna in $A$ con certezza. Sostituendo la seconda nella prima:

$$V^{\pi_1}(A) = 2 + 0{,}81 \, V^{\pi_1}(A) + 0{,}09 \cdot 0{,}9 \, V^{\pi_1}(A) = 2 + 0{,}891 \, V^{\pi_1}(A)$$

$$0{,}109 \, V^{\pi_1}(A) = 2 \quad \Longrightarrow \quad V^{\pi_1}(A) = \frac{2}{0{,}109} \approx 18{,}35, \qquad V^{\pi_1}(B) = 0{,}9 \cdot 18{,}35 \approx 16{,}51$$

Come previsto, $\pi_1$ batte nettamente la policy pigra $\pi_0$ in entrambi gli stati ($18{,}35 > 10$ e $16{,}51 > 10$): quindi $\pi_1 \geq \pi_0$, con disuguaglianza stretta ovunque.

9.4 Valutazione della policy audace e confronto#

Sia $\pi_2$ la policy: cerca in entrambi gli stati, cioè continua a cercare anche con la batteria bassa. Cercare da $B$ ha reward atteso

$$r(B, \text{cerca}) = 0{,}6 \cdot 2 + 0{,}4 \cdot (-3) = 1{,}2 - 1{,}2 = 0$$

il guadagno delle ricerche fortunate è esattamente cancellato, in media, dal costo dei soccorsi. Le equazioni di Bellman:

$$V^{\pi_2}(A) = 2 + 0{,}9 \left[ 0{,}9 \, V^{\pi_2}(A) + 0{,}1 \, V^{\pi_2}(B) \right]$$

$$V^{\pi_2}(B) = 0 + 0{,}9 \left[ 0{,}6 \, V^{\pi_2}(B) + 0{,}4 \, V^{\pi_2}(A) \right]$$

Dalla seconda equazione: $V^{\pi_2}(B) = 0{,}54 \, V^{\pi_2}(B) + 0{,}36 \, V^{\pi_2}(A)$, da cui $0{,}46 \, V^{\pi_2}(B) = 0{,}36 \, V^{\pi_2}(A)$ e quindi $V^{\pi_2}(B) \approx 0{,}783 \, V^{\pi_2}(A)$. Sostituendo nella prima:

$$V^{\pi_2}(A) = 2 + 0{,}81 \, V^{\pi_2}(A) + 0{,}09 \cdot 0{,}783 \, V^{\pi_2}(A) = 2 + 0{,}8804 \, V^{\pi_2}(A)$$

$$0{,}1196 \, V^{\pi_2}(A) = 2 \quad \Longrightarrow \quad V^{\pi_2}(A) \approx 16{,}73, \qquad V^{\pi_2}(B) \approx 13{,}09$$

Il confronto con $\pi_1$ è netto: $V^{\pi_1}(A) \approx 18{,}35 > 16{,}73$ e $V^{\pi_1}(B) \approx 16{,}51 > 13{,}09$. La policy prudente domina quella audace in tutti gli stati, quindi $\pi_1 \geq \pi_2$ nell’ordinamento delle policy.

Si noti che il danno dell’audacia si propaga anche allo stato $A$, dove le due policy fanno la stessa cosa: partire da $A$ con $\pi_2$ vale meno perché prima o poi si scenderà in $B$, e lì $\pi_2$ si comporta peggio. È l’effetto a lungo termine catturato dalla ricorsione di Bellman.

9.5 Verifica di ottimalità#

Resta da stabilire se $\pi_1$ sia la policy ottima. Invece di valutare le 6 policy una per una, si usa il criterio delle equazioni di ottimalità: si calcola $Q^{\pi_1}(s, a)$ per tutte le azioni (anche quelle che $\pi_1$ non usa) con la relazione $Q^{\pi_1}(s,a) = r(s,a) + \gamma \sum_{s'} p(s' \mid s, a) V^{\pi_1}(s')$, e si controlla se $\pi_1$ è greedy rispetto alla propria value function. Usando $V^{\pi_1}(A) \approx 18{,}35$ e $V^{\pi_1}(B) \approx 16{,}51$:

• Stato $A$:

$$Q^{\pi_1}(A, \text{cerca}) = 2 + 0{,}9 \left( 0{,}9 \cdot 18{,}35 + 0{,}1 \cdot 16{,}51 \right) \approx 18{,}35$$

$$Q^{\pi_1}(A, \text{attendi}) = 1 + 0{,}9 \cdot 18{,}35 \approx 17{,}51$$

• Stato $B$:

$$Q^{\pi_1}(B, \text{ricarica}) = 0 + 0{,}9 \cdot 18{,}35 \approx 16{,}51$$

$$Q^{\pi_1}(B, \text{attendi}) = 1 + 0{,}9 \cdot 16{,}51 \approx 15{,}86$$

$$Q^{\pi_1}(B, \text{cerca}) = 0 + 0{,}9 \left( 0{,}6 \cdot 16{,}51 + 0{,}4 \cdot 18{,}35 \right) \approx 15{,}52$$

In $A$ l’azione con $Q$ massimo è cerca ($18{,}35 > 17{,}51$), che è esattamente ciò che $\pi_1$ prescrive; in $B$ l’azione con $Q$ massimo è ricarica ($16{,}51 > 15{,}86 > 15{,}52$), di nuovo la scelta di $\pi_1$. Dunque in ogni stato vale $V^{\pi_1}(s) = \max_a Q^{\pi_1}(s, a)$: la value function di $\pi_1$ soddisfa l’equazione di ottimalità di Bellman. Poiché $V^{*}$ è l’unica soluzione di quell’equazione (per la proprietà di contrazione di $T^{*}$), si conclude che

$$V^{\pi_1} = V^{*}, \qquad \pi_1 = \pi^{*}$$

La policy prudente è la policy ottima di questo MDP, ed è deterministica, come garantito dal teorema di esistenza. Si osservi anche il ruolo diagnostico dei valori $Q$: la differenza $V^{\pi_1}(B) - Q^{\pi_1}(B, \text{cerca}) \approx 0{,}99$ quantifica esattamente quanto costerebbe, in return atteso, una singola deviazione verso la ricerca azzardata in $B$.

In parole semplici: per certificare che una strategia è la migliore possibile non serve confrontarla con tutte le altre: basta controllare, stato per stato, che nessuna singola mossa alternativa abbia un $Q$ più alto. Se nessuna deviazione di un solo passo conviene, allora nessuna strategia alternativa, per quanto complicata, può fare meglio: è tutto il potere della ricorsione di Bellman.

Glossario#

Termine	Definizione
Feedback valutativo	Segnale che valuta la qualità dell’output prodotto, senza indicare l’output corretto; caratterizza il RL in contrapposizione al feedback istruttivo del supervisionato.
Agente	L’entità che apprende e decide: osserva lo stato, sceglie le azioni, riceve i reward.
Ambiente	Tutto ciò che è esterno all’agente: riceve le azioni e restituisce nuovo stato e reward.
Stato ($S_t$)	Descrizione della situazione corrente dell’ambiente, base per la decisione dell’agente.
Azione ($A_t$)	Scelta dell’agente al passo $t$; l’insieme disponibile $\mathcal{A}(s)$ può dipendere dallo stato.
Reward ($R_{t+1}$)	Valutazione numerica immediata dell’effetto di un’azione.
Delayed reward	Fenomeno per cui il segnale che certifica la bontà di una decisione arriva molti passi dopo la decisione stessa.
Proprietà di Markov	Stato e reward successivi dipendono solo da stato e azione correnti, non dalla storia; è una proprietà della definizione di stato.
Processo di Markov	Tupla $\langle \mathcal{S}, P \rangle$: evoluzione casuale tra stati senza azioni né reward.
Markov Reward Process (MRP)	Tupla $\langle \mathcal{S}, P, R, \gamma \rangle$: processo di Markov arricchito con reward e discount.
MDP	Tupla $\langle \mathcal{S}, \mathcal{A}, P, R, \gamma \rangle$: MRP con azioni che controllano transizioni e reward.
Dinamica one-step	Distribuzione $p(s', r \mid s, a)$ che definisce completamente un MDP.
Ipotesi del reward	Assunzione che ogni obiettivo sia esprimibile come massimizzazione della somma attesa di un segnale scalare.
Return ($G_t$)	Somma (scontata) dei reward futuri, $G_t = \sum_k \gamma^k R_{t+k+1}$; l’agente massimizza $\mathbb{E}[G_t]$.
Task episodico / continuo	Interazione che termina in uno stato terminale / che prosegue indefinitamente.
Discount factor ($\gamma$)	Fattore in $[0,1]$ che sconta i reward futuri: rende finito il return e regola la lungimiranza dell’agente.
Stato assorbente	Stato da cui non si esce e che produce reward zero; unifica task episodici e continui.
Policy ($\pi$)	Funzione di decisione dell’agente: deterministica $\pi(s)$ o stocastica $\pi(a \mid s)$.
Policy Markoviana / stazionaria	Dipende solo dallo stato corrente / non cambia nel tempo.
State-value function ($V^{\pi}$)	Return atteso da uno stato seguendo $\pi$: $V^{\pi}(s) = \mathbb{E}_{\pi}[G_t \mid S_t = s]$.
Action-value function ($Q^{\pi}$)	Return atteso eseguendo $a$ in $s$ e poi seguendo $\pi$: $Q^{\pi}(s,a) = \mathbb{E}_{\pi}[G_t \mid S_t = s, A_t = a]$.
Equazione di aspettativa di Bellman	Decomposizione ricorsiva $V^{\pi}(s) = \sum_a \pi(a \mid s) [r(s,a) + \gamma \sum_{s'} p(s' \mid s,a) V^{\pi}(s')]$: sistema lineare in $\vert \mathcal{S}\vert$ incognite.
Policy evaluation	Calcolo di $V^{\pi}$ per una policy data; in forma chiusa $V^{\pi} = (I - \gamma P^{\pi})^{-1} R^{\pi}$, costo $O(\vert \mathcal{S}\vert ^3)$.
Operatore di Bellman ($T^{\pi}$, $T^{*}$)	Operatore di backup a un passo sulle funzioni di valore; è una $\gamma$-contrazione in norma del massimo, con punto fisso unico ($V^{\pi}$ o $V^{*}$).
Ordinamento tra policy	$\pi \geq \pi'$ se $V^{\pi}(s) \geq V^{\pi'}(s)$ in ogni stato; è un ordinamento parziale.
Value function ottime ($V^{*}$, $Q^{*}$)	Massimo di $V^{\pi}$ e $Q^{\pi}$ su tutte le policy, stato per stato.
Policy ottima ($\pi^{*}$)	Policy migliore o uguale a tutte le altre; in ogni MDP ne esiste almeno una deterministica.
Equazioni di ottimalità di Bellman	$V^{*}(s) = \max_a [r(s,a) + \gamma \sum_{s'} p(s' \mid s,a) V^{*}(s')]$; sistema non lineare per il $\max$, senza soluzione in forma chiusa.
Policy greedy	Policy che in ogni stato sceglie l’azione con valore massimo; greedy rispetto a $Q^{*}$ dà $\pi^{*}$.
Credit assignment	Problema di attribuire ai singoli passi di una sequenza il merito del risultato finale.

---

1. Correzione flaggata: la slide riporta “$\gamma = 1$” sotto questo esempio, ma i valori mostrati sono quelli di Sutton e Barto per $\gamma = 0{,}9$ (si verifichi $V^{*}(A) = 24{,}4 = 10 + 0{,}9^5 \cdot 24{,}4$, coerente con il ciclo ottimo di 5 passi $A \to A' \to \dots \to A$). Con $\gamma = 1$, in un task continuo come questo, il return non sarebbe nemmeno finito.↩︎

Dispensa Machine Learning · Politecnico di Milano